The subject invention relates to securing cryptographic systems against external attacks. More particularly it relates to reducing the amount of information which can be discovered by external monitoring of a system performing cryptographic operations (e.g. monitoring of external electromagnetic fields or power consumption for such a system). Hereinafter such external attacks are sometimes referred to as “side channel” attacks.
Cryptographic systems perform operations such as encryption, decryption, and generation of digital signatures by operating on messages, or information derived from the messages with keys which, in general, must be maintained as secret. Such keys (hereinafter sometimes “secret keys”) can be a symmetric keys such as those used with known encryption protocols such as DES, or the private key of an asymmetric key pair such as those used with known public key encryption protocols such as RSA. As used herein secret keys also include temporary, or ephemeral, keys that are derived from secret information, used for a limited period and replaced with a new key derived from the same information. Such ephemeral keys are used in known digital signature protocols such as ECDSA. It has been shown that knowledge of an ephemeral key, publicly known parameters, and the public key is sufficient to compromise the secret information used with protocols such as ECDSA.
A fundamental process common to all such cryptographic systems is the process of a one-way function. Generally, a one-way function f is a function such that, given y and f, it is infeasible to find x such that f(x)=y. A process used in a number of the cryptographic systems as a one-way function is that of iteratively generating a value H by setting H=G. (where G is a digital value, and is taken as an element, hereinafter sometimes “point,” of a set) then repeating the calculation H=H[op]G d−1 times, where d is an integer utilized as a secret key. Where the binary operation [op] is addition this process is called scalar multiplication. Where the binary operation [op] is multiplication this process is called exponentiation. As used hereinafter the terms “addition”, “multiplication”, and “exponentiation” correspond to the signs “+”, “−”, and “^”, respectively.
Various cryptographic systems such as those described above and, in particular uses of such one way functions in such systems, are well known and need not be described further here; except to note that naive methods using d−1 successive additions or multiplications generally are too slow, and that various more efficient methods have been developed. A particularly efficient type of method is the fixed window type.
FIG. 1 illustrates the prior art computation of a scalar multiplication d·G using the fixed window method. A similar process exists for modular exponentiation. Initially, at step 10, parameters W, a window width, and d, an integer value used as a secret key, are determined and G, a digital value from a defined set over which the binary operation [op] is defined, is input. Then, at step 12, d is expressed as a sequence of k windows (i.e., binary integers W bits in length) di such that dk−1dk−2 . . . d0 expresses d in base 2W.
Then at steps 14 through 20, values Gi are precomputed. At step 14 i is set equal to 0. At step 16 value Gi is set equal to 2iWG, and i is incremented by 1. At step 20, if i<k, the method returns to step 16; otherwise the precomputation ends. It will be apparent to those skilled in the art that steps 10 through 20 need only be performed once and that the results can be stored for use in later operations.
After precomputation of values Gi, actual computation of d·G begins at step 22; where values A and B are set equal to an identity element in the set, usually denoted by 0 when the underlying binary operation is addition; or 1 when the binary operation is multiplication ; and in the generic case by I, and index j is set equal to 2W−1. The identity element I has a special property in the set from which G is a member in that regardless of the selected value G from the set G[op]I=I[op]G=G. Then at step 24 index i is set equal to 0 (beginning the jth round of computation), and at step 28 the method determines if window di is equal to j. If so it goes to step 30 and sets B equal to B+Gi, and then, at step 32 increments index i by 1. Otherwise, if window di is not equal to j the method goes directly to step 32.
After step 32, at step 36, the method determines if index i is equal to k. If not it returns to step 28 and again determines if window di is equal to j. Otherwise, at steps 38 and 40, the method sets value A=A+B and decrements index j by 1.
Then at step 44 the method determines if index j is greater than 0. If so, it returns to step 24, resets index i to 0 (and begins the (j−1)th round of computation). Otherwise, at step 46 the method returns value A, equal to d·G, and ends. The value A can be used as a public key or used as part of a digital signature for cryptographic operations.
FIG. 2 shows hypothetical values which illustrate, in simplified form, a typical externally detectable signal (e.g. power variation, or external electromagnetic field) generated by a cryptographic system in calculating 98·G, with W=2; with time and amplitude expressed in arbitrary units. Hereinafter numbers in the form nnnnbm are to be understood as being expressed in base m; numbers without subscript are to be understood as decimal numbers.
Decimal 98=0100010b2; and width W=2 gives windows:
d3=01|d2=10|d1=00|d0=10, or 1202b4. Examination of FIG. 2 shows that these values can readily be recovered by a side channel attack. From time 1 through time 6 initialization takes place steps 10 through 20 of FIG. 1). Little useful information is generated in the externally detectable signal during this period. Beginning at time 6 rounds j=3, j=2, and j=1 are computed in that sequence. Each round is delimited by peaks 50-3, 50-2, and 50-1 which occur substantially as the method loops through step 38, setting A=A+B at the end of each round. (It should be noted that peaks 50-3, 50-2, and 50-1 are shown as having a different amplitude from other peaks in FIG. 2, but, even if this were not so, these peaks can readily be identified by the regularity of their timing.) From inspection of the method of FIG. 1 it is readily seen that the decision, at step 28, whether or not to execute step 30, setting B=B+Gi, and generating an externally detectable peak, occurs at substantially the same time within each round. From this FIG. 2 immediately shows:                for j=3 no peaks indicates that no di=3, implying d=????b4;        for j=2 peaks 52-2 and 52-0 indicate that d2=d0=2, implying d=?2?2b4;        for j=1 peak 52-3 indicates that d3=1, implying d=12?2b4;        by elimination d1=0, implying d=1202b4=decimal 98;thus showing that a side channel attack can readily yield the value used as the secret (or ephemeral) key d, i.e., decimal 98.        
One approach to protecting cryptographic systems from side channel attacks is to physically shield the system so that external signals are more difficult to detect. Shielding however is not always feasible either because of the cost or because of physical limitations inherent in the system application. (e.g. Smart cards, which are mass market products intended to be carried by the user and so must be both low cost and small.) Further, continuing advances in signal processing techniques make it possible to recover information from signals with ever lower signal to noise ratios; making the protection offered by physical shielding increasingly uncertain over time. Another approach is to design computational methods that reduce the information contained in externally detectable signals. Techniques for doing this are described, for example, in U.S. Pat. 6,298,442 issued to Kocher et al. for Secure Modular Exponentiation with Leak Minimization for Smartcards and Other Cryptosystems, which describes various techniques used in methods which are resistant to side channel attacks.
While techniques such as those described in the above '442 patent are believed generally useful they are not believed to provide maximal protection for fixed window methods, as will be described below. Thus it is an object of the subject invention to provide a method and system for implementing a fixed window method for iteratively generating a value [op] dG; the method having increased resistance to side channel attacks.